Computer-based authentication systems have been used to authenticate users before providing access to computer systems, devices, and physical locations. Such systems typically make use of one or more of something a user has (such as a physical object or token), something the user knows (such as a secret), or a physical characteristic of the person (e.g. fingerprints, retina patterns, etc.).
Passwords are an example of something a person knows. They are easy to use and conceptually simple. Because they are generally alphanumeric in form and often closely related to words in natural language, passwords are relatively easy for users to remember. Typically, users can rapidly enter them through standard hardware peripherals such as keyboards. Nonetheless, in terms of their security properties, passwords have shortcomings. Typically, users derive their passwords from a limited portion of the lexicons in their native languages, making them easy to guess, particularly in automated computer attacks. An attack in which common passwords are used to guess a password is known as a dictionary attack.
The vulnerability of passwords in computer systems is becoming increasingly problematic as computing and networking technologies aim to manage increasingly sensitive information. Consumers are beginning to use smart cards and other portable devices to carry digital cash. At the same time, corporations are making sensitive information more available on their networks and are employing digital signatures in committing to legally binding contracts. Hardware devices like smart cards and authentication tokens provide cryptographic authentication for such applications; but typically the cryptographic features of these devices are secured using passwords.
It is possible to broaden the distribution of passwords that are used in a system, and thereby strengthen the system by assigning randomly generated alphanumeric passwords to users. Even users with the most retentive memories, however, have difficulty remembering more than approximately seven alphanumeric characters. The total number of such seven character passwords is about 235≈1011, which is too small to provide resistance against an automated computer attack on the password. Strong resistance to automated password attacks requires a password space on the order of about 270≈1021. This space corresponds to random, alphanumeric passwords of sixteen characters in length, which is too long for practical use by most users.
While users may have difficulty remembering passwords made up of a random alphanumeric strings, particularly if they must remember several such passwords, they may not have as much difficulty remembering other types of information or similar information in other contexts. A few examples of the other types of nonpassword data an individual may routinely remember are historical and personal events, the configuration of rooms in buildings, and the layout of city streets, not to mention the vocabulary and idioms of her native language. Some of that information may remain fixed in her memory over extended periods of time, even without frequent reinforcement.
A number of researchers have investigated the use of such everyday information in connection with mnemonic systems as a replacement for passwords. One authentication approach exploits the ability of users to recognize faces. To authenticate herself in this system, a user is asked to identify a set of familiar faces from among a gallery of photographs. While conveniently universal, this system has large memory requirements for the storage of the photographs, and has relatively slow data entry time. Another proposed approach is based on the use of routes on a complex subway system, such as the Tokyo subway system, in connection with secrets, suggesting that users could retain relatively large amounts of information in this context. This approach has the advantage of mnemonic naturalness, but has a strong disadvantage in its idiosyncrasy because not all users live in cities with subway systems or use a subway frequently.
A commercial system produced by Passlogix, Inc. of New York, N.Y. effectively extends the mnemonic approach by allowing users to select from a range of mnemonic systems. Users can, for instance, choose to use an interface displaying a room containing a collection of valuables, and encode a password as a sequence of moves involving the hiding of these valuables in various locations around the room. This method of password entry appeals to a natural mnemonic device because it resembles the medieval system of the “memory palace,” whereby scholars sought to archive data mentally in an imagined architectural space. By allowing the user to select a password herself, however, this approach is vulnerable to the problem of predictability that occurs with conventional password systems. Some passwords are more popular than others, since they are easier to remember. In one example, one-third of user-selected passwords could be found in the English dictionary. Similarly, in a mnemonic system, users are more likely to pick some sequences than others. In one example, a mnemonic system allows users to trade stocks; typically, the users will choose from among the most popular stocks, as these are the easiest to remember. In seeking to guess a password in this system, an attacker is likely to gain a substantial advantage by choosing Dow Jones stocks. In principle, if user passwords are formed as sufficiently long random sequences of moves, a mnemonic system will provide an adequate level of cryptographic security. Typically, mnemonic systems are not designed to facilitate user memorization of random sequences, and may not even enforce a minimum sequence length in user password entry. A mnemonic system may also be cumbersome in terms of the user interaction involved in entering a password, in some cases demanding an involved sequence of non-uniform mouse movements to enter the password into a computer system.
Implementations of authentication systems typically use cryptographic protocols that are conventionally predicated on exact knowledge. An authentication system using RSA signatures, for example, derives its security largely from the presumption that a legitimate user with public key (N, e) possesses a corresponding secret key of the uniquely specifiable form (N, d). There are situations, however, in which human and other factors undermine the possibility of exactness in a security system. For example, in biometric systems in which users identify themselves by means of fingerprint features, variability in user interaction is such that a finger is rarely read exactly the same way twice. Moreover, there are situations in which although the original information in a system is exact, its transmission may only be approximate. For example, users typically make typing errors when entering passwords on keyboards. Similarly, data transmission channels are often subject to random noise.
An element of some cryptographic protocols is referred to as a bit commitment scheme. In a conventional bit commitment scheme, one player, whom we denote the sender, aims to conceal a bit b. The sender produces an encryption of b, denoted by y, and sends y to a second player, known as the receiver. Generally, a bit commitment scheme is such that it is infeasible for the second player to learn the bit b. Additionally, the sender later “opens” the commitment y, that is, proves to the receiver that y indeed represents an encryption of b. It is generally only feasible, however, for the sender to “open” y in one way, that is, to decrypt a unique value of b. We may view this, intuitively, as a process whereby the sender places the bit b in a safe and gives the safe to the receiver. Only the sender can open the safe, since she alone knows the combination. Moreover, she cannot change the value contained in the safe while it is in the keeping of the receiver.
An example of a bit commitment scheme is the storage of the hash of user's password in a UNIX file accessible only to the UNIX system administrator. Since the system administrator only has access to the hash of the password, the system administrator does not know what the user's plaintext password is. Nonetheless, when the user provides a password for authentication, the system administrator can compare the hash of the provided password to the stored hash and, if the hashes match, confirm that the user has provided the proper password. Bit commitment may alternatively be done, for example, using a symmetric encryption algorithm, an asymmetric encryption algorithm, a pseudo-random sequence generator, or any other one-way function.
Formally, a bit commitment scheme consists of a function F: {0, 1}×X→Y. To commit a bit b, the sender chooses a witness x∈X, generally uniformly at random. The sender then computes y=F(b, x). This value y is known as a blob. It represents the bit b sealed in a “safe”. To “open” or decommit the blob y, the sender produces the bit b and the witness x. The blob is successfully opened if the receiver has been convinced that y indeed represents an encryption of b. A bit commitment scheme is said to be concealing if it is infeasible for the receiver to guess b with probability significantly greater than ½. It is said to be binding if it is infeasible for the sender to decommit the blob y with the incorrect bit, that is, with (1−b). It is possible to deploy a bit commitment scheme as a commitment scheme on an arbitrarily long string of bits by committing each bit independently. The term commitment scheme shall refer to a scheme that involves commitment of a bit string c (or other potentially non-binary value) in a single blob, and for which it is possible to extract c efficiently given a witness for the blob. Thus we assume F: C×X→Y, where C is some potentially non-binary space.
Vendors of biometric authentication systems have for some time recognized the importance of achieving a practical system that stores biometric information in a non-explicit, protected form and that also can tolerate some corruption in subsequent biometric readings. To this end, the Mytec Technologies Inc. has developed an encryption process in which biometric information serves as an unlocking key. Sold under the brand name Bioscrypt™, Mytec Technologies's process overcomes the problem of corruption in biometric readings by means of Fourier transforms. While fairly efficient, however, the Bioscrypt™ process carries no rigorous security guarantees.
Davida, Frankel, and Matt have proposed a system in which a biometric template is stored in non-explicit, protected form. The Davida et al. system, described in “On Enabling Secure Applications Through Off-Line Biometric Identification,” IEEE Symposium on Privacy and Security (May 5, 1998), requires multiple biometric readings from which the check bits may be derived. A hash of the Davida et al. template which includes the check bits is then stored. The multiple biometric readings required by the Davida et al. system may be too time-consuming to be practical or attractive for many real-world applications. Further, the Davida system does not have the necessary error tolerance to work in many real-world applications.